给定一个字符串s,字符串s只包含以下三种字符: (,*,),请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:
1.左括号'('必须有对应的右括号')'
2.右括号')'必须有对应的左括号'('
3.左括号必须在对应的右括号前面
4.*可以视为单个左括号,也可以视为单个右括号,或者视为一个空字符
5.空字符串也视为合法的括号字符串
数据范围:
"()()"
true
"((*)"
true
"(*)"
true
"(((*)"
false
function isValidString(s) { var stack = []; var sArr = s.split(''); // 处理右括号 for(var i = 0; i < sArr.length; i++) { var item = sArr[i]; if(item === '(' || item === '*') { stack.push(item); } // 遇到右括号时,从栈里面去找最近的左括号,若找不到,则找最近的*号, 若依然找不到,则字符串无效 if(item === ')') { var _stack = [...stack].reverse(); // 若栈为空,则字符串无效 if(_stack.length === 0) { stack.push(-1); break; } // 寻找最近的左括号或左星号,都没有,则字符串无效 var index = _stack.indexOf('(') > -1 ? _stack.indexOf('(') : _stack.indexOf('*'); if(index === -1) { break; } // 将最近的左括号或左星号替换为空 stack[stack.length - index -1] = ''; } } stack = stack.filter(item => item !== ''); // stack数组情况,可能存在多余的左括号( 和 多余的星号,将(和*相互抵消 for(var j = stack.length - 1; j >= 0; j--) { if(stack[j] === '(') { // 检查元素右侧是否存在星号,若存在,则将 var starIndex = stack.indexOf('*',j); if(starIndex > -1) { stack[j] = ''; stack[starIndex] = ''; } else { break; } } } return stack.join('').replaceAll('*','').length === 0; }